﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution72
{
    //状态转移一下
    public int MinDistance(string word1, string word2)
    {

        int m = word1.Length;
        int n = word2.Length;
        int[][] dp = new int[m + 1][];//dp[i][j]是长度为i和j的两个子串，有多少公共子序列
        //多一维是为了表示空字符串，dp[0][0]是两个空字符串
        for (int i = 0; i <= m; i++)
        {
            dp[i] = new int[n + 1];
            dp[i][0] = i;//删除i个

        }
        for (int j = 0; j <= n; j++)
        {
            dp[0][j] = j;//删除j个

        }
        //三种操作
        //1，a插入，前一个状态dp[i - 1][j]，dp[i][j] = dp[i - 1][j]+1
        //2，a删除=b插入，前一个状态dp[i][j- 1]，dp[i][j] = dp[i][j - 1]+1
        //3，a替换，如果a和b的字符相同，不需要操作dp[i][j] = dp[i-1][j - 1]
        //  a替换，如果a和b的字符不相同，需要操作，dp[i][j] = dp[i-1][j - 1]+1


        //如果我们知道 hors 到 ro 的编辑距离为 c，
        //那么显然 horse 到 ros 的编辑距离不会超过 c + 1，原因同上。
        //这里解释了为什么dp[i][j] = dp[i-1][j - 1]+1，
        //hors到ro距离为c，所以horse到roe距离也为c，不需要操作dp[i][j] = dp[i-1][j - 1]
        //horse到roe距离为c，所以horse到ros距离也为c+1,把s换成e,需要操作，dp[i][j] = dp[i-1][j - 1]+1

        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                int a = dp[i - 1][j] + 1;
                int b = dp[i][j - 1] + 1;
                int c=Math.Min(a, b);
                if (word1[i - 1] == word2[j - 1])
                {
                    dp[i][j] = Math.Min(c, dp[i - 1][j - 1]); //不需要操作
                }
                else
                {
                    dp[i][j] = Math.Min(c, dp[i - 1][j - 1]+1);
                }


            }
        }
        return dp[m][n];

    }
}
class Program72
{
    static void Main72(string[] args)
    {
        Solution72 solution = new Solution72();
        string word1 = "horse", word2 = "ros";
      int res=  solution.MinDistance(word1, word2);
        Console.WriteLine(res);
    }
}
